我要招人

去企业版

首页 > 试题广场 >

括号生成

[编程题]括号生成

热度指数：58736 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围： $0 \le n \le 10$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(2^n)$

示例1

输入

输出

["()"]

示例2

输入

输出

["(())","()()"]

算法知识视频讲解

Python 3

牛客116003403号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @auther zhangjunyi
# @time  20230309
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> list[str]:
        # write code here

        #定义L1符号列表

        L1 =["(",")"]

        #定义L2收集每个步骤的括号生成的结果,初始化为空
        L2=[]

        #定义L3收集总共生成的结果，初始化为空

        L3=[]
        L4=[]


        #定义变量i，j表示左右括号在L2中的数量，初始化为0

        i=0

        j=0


        #定义回朔函数当j<i的时候，可以添加右括号，也可以添加左括号，用回朔法进行添加
        def traversal(i,j,L1,L2):

            if j==i  and i==n:
                L4.append(L2.copy())
                return 
            for x in L1:
                                    
                if x=="(" and  i<n:
                    L2.append(x)
                    i+=1
                    traversal(i,j,L1,L2)
                    i-=1
                    L2.pop()

                    
                elif x==")" and j<i :
                    L2.append(x)
                    j+=1
                    traversal(i,j,L1,L2)
                    j-=1
                    print(L2)
                    print(L2[-1])
                    L2.pop()
            

            return L4


        L4 = traversal(i,j,L1,L2)
        for x in L4:
            L3.append("".join(x))
        return L3

发表于 2023-03-09 14:35:16 回复(0)

Python 3

牛客1217718号

class Solution:
    def generateParenthesis(self , num: int) -> List[str]:
        res = []
        if num == 1:
            return ["()"]
        result = self.generateParenthesis(num - 1)
        for item in result:
            res.append("(" + item + ")")
            # 插到左边
            res.append("()" + item)
            # 插到右边
            res.append(item + "()")
            # 插到中间
            for i in range(len(item)//2):
                res.append(item[:i] + "()" + item[i:])
        return list(set(res))

发表于 2023-02-18 11:22:29 回复(0)

Python 3

Vivimore

class Solution:
    def recursion(self, left, right, temp, n, res):
        if left == n and right == n:
            res.append(temp)
            return 
        if left < n:
            self.recursion(left + 1, right, temp + '(', n, res)
        if right < n and left > right:
            self.recursion(left, right + 1, temp + ')', n, res)

    def generateParenthesis(self , n: int) -> List[str]:
        res = []
        temp = ''
        self.recursion(0, 0, temp, n, res)
        return res

发表于 2022-05-20 19:38:57 回复(0)

Python 3

宫城良田z

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        '''
        与全排列不同, 不需要首先生成再排序输出.
        '''
        def dfs(res, cur: str):
            if len(cur) == n * 2 and cur.count(')') == cur.count('('):
                res.append(cur)
            if cur.count(')') > cur.count('('): return # 递归过程中右括号数一定小于左括号数.
            if cur.count('(') > n: return

            dfs(res, cur + '(')
            dfs(res, cur + ')')

        res = []
        dfs(res, '')
        return res

发表于 2022-04-30 16:05:59 回复(0)

Python 3

神圣之风

https://www.bilibili.com/video/BV1c54y1S7iN?spm_id_from=333.337.search-card.all.click

class Solution:
def generateParenthesis(self , n: int) -> List[str]:

rst=[]
self.foo(n,"",rst)
return(rst)

def foo(self,n,s,rst):
if(len(s)==2*n):
rst.append(s)
left_num,right_num=s.count("("),s.count(")")
if(left_num<n):#只要左括号数量小于n，都可以添加左括号
self.foo(n,s+"(",rst)
if(right_num<left_num):#只要有括号数量小于n,都可以添加有括号
self.foo(n,s+")",rst)

发表于 2022-04-14 20:32:03 回复(0)

Python 3

梦幻泡影oO

递归

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        ret = []
        tmp = []
        
        def dfs(i, j):
            if i < j:
                return
            if i == n and j == n:
                ret.append(''.join(tmp))
            
            if i <= n:
                tmp.append('(')
                dfs(i + 1, j)
                tmp.pop()
            if j <= n:
                tmp.append(')')
                dfs(i, j + 1)
                tmp.pop()
            
        dfs(0, 0)
        return ret

发表于 2022-02-15 23:48:25 回复(0)

Python 3

Joy_9

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        res=[]
        def bfs(paths,left,right):
            if left>n&nbs***bsp;right>left:
               return
            if len(paths)==2*n:
                res.append(paths)
                return
            bfs(paths+'(',left+1,right)
            bfs(paths+')',left,right+1)
        bfs('',0,0)
        return res

发表于 2022-01-20 07:59:10 回复(0)

Python 3

可恶，被他装到了

#
#
# @param n int整型
# @return string字符串一维数组
#
class Solution:
def generateParenthesis(self , n ):
order = 0
bracket_list,left_bracket = [],[]
while order < 2*n:
bracket_list,left_bracket = self.brackets(n, bracket_list, left_bracket)
order += 1
return bracket_list

def brackets(self, n, bracket_list, left_bracket):
if len(left_bracket) == 0:
bracket_list.append("(")
left_bracket.append(1)
return bracket_list,left_bracket
else:
new_bracket_list = []
new_left_bracket = []
for index,leftnum in enumerate(left_bracket):
if leftnum > 0 and bracket_list[index].count("(") < n:
new_bracket_list.append(bracket_list[index] + "(")
new_left_bracket.append(leftnum + 1)
new_bracket_list.append(bracket_list[index] + ")")
new_left_bracket.append(leftnum - 1)
elif leftnum == 0:
new_bracket_list.append(bracket_list[index] + "(")
new_left_bracket.append(leftnum + 1)
else:
new_bracket_list.append(bracket_list[index] + ")")
new_left_bracket.append(leftnum - 1)
return new_bracket_list, new_left_bracket

# write code here

发表于 2021-08-26 22:37:00 回复(0)

Python 3

VincentLau~

class Solution:
    def generateParenthesis(self , n ):
        # write code here
        self.res = []
        def dfs(l, r, tmp):
            if l==0 and r == 0:
                self.res.append(tmp)
                return
            if l > r:
                return 
            if l> 0:
                dfs(l-1, r, tmp+'(')
            if r > 0:
                dfs(l, r-1, tmp+')')
        dfs(n, n, "")
        return self.res

发表于 2021-08-12 15:04:20 回复(0)